Module# 06: Stack Lecture#22: Programming
for Stack
/* The following set
of definitions followed by the main class illustrates the array implementation
of stack. */
// Example 22.1:
Defining the class stack using array
// Example 22.2:
Defining the method push()
// Example 22.3:
Defining the method pop()
// Example 22.4:
Defining the method isEmpty()
// Example 22.5:
Defining the method printStack()
// Example 22.6:
Basic stack operations using the class StackA
// Example 22.1:
Defining the class stack using array
import java.util.*;
class StackA<T> {
T[] data;
int length;
int top;
Stack_A(T[] a) {
data = a;
length = a.length;
top = -1;
}
// Example 22.2:
Defining the method push()
void push(T a) {
if(top < length-1) {
top++;
data[top] = a;
}
else {
System.out.println("Stack
Overflow");
}
}
// Example 22.3:
Defining the method pop()
T pop() {
T a = null;
if(top == -1) {
System.out.println("Stack Underflow
");
}
else {
a = data[top];
top--;
}
return a;
}
// Example 22.4:
Defining the method isEmpty()
boolean isEmpty() {
if(top == -1) {
return true;
}
else {
return false;
}
}
// Example 22.5: Defining the method printStack()
void printStack() {
if(top == -1) {
System.out.println("Stack
Empty");
}
else {
for(int i = top; i>=0 ; i--) {
System.out.print(data[i] + " ");
}
System.out.println();
}
} // End of the
definition of class StackA
// Example 22.6:
Basic stack operations using the class StackA
/* This is the main program, illustration the
usage of the class defined. */
class StackAImplementationDemo
{
public static void main(String[] args) {
Integer
a[] = new Integer[2];
StackA<Integer> st = new StackA<Integer>(a);
st.push(5);
st.printStack();
st.push(6);
st.push(7);
st.printStack();
st.pop();
st.printStack();
st.pop();
st.printStack();
st.pop();
System.out.println(“ Is empty? “ + st.isEmpty();
}
} // End of the demo class
/* The following set
of definitions followed by the main class illustrates the linked list
implementation of stack. */
// Example 22.7:
Defining the class stack using linked list
// Example 22.8:
Defining the method push()
// Example 22.9:
Defining the method pop()
// Example 22.10:
Defining the method isEmpty()
// Example 22.11:
Defining the method printStack()
// Example 22.12:
Basic Stack operation using the class StackL
// Example 22.7:
Defining the class stack using linked list
// This program shows
how a stack can be defined using a linked list
/* import jLLPacakge;
This program uses linked list related
implementation; so, include the directory (e.g., jLLPackage,
where all those programs are defined. */
// This program shows
how a stack can be defined using a linked list
class StackL<T> {
JLinkedList<T> top; // Header to the list
int t; // Length of the list
StackL() {
top
= new JLinkedList<T>();
t
= 0;
}
// Example 22.8:
Defining the method push()
/* This definition
assumes the linked list implementation as discussed in Lecture# 20; Assume that
the programs are maintained in the directory: jLLPackage
folder. */
void push(T data) {
t
+= 1;
this.top.insertFront(data); //Suppose, this method is available in jLLpackage
}
// Example 22.9:
Defining the method pop()
/* This definition
assumes the linked list implementation as discussed in Lecture# 20; Assume that
the programs are maintained in the directory: jLLPackage
folder. */
T pop() {
T
data = null;
If
(!isEmpty()) {
t
-= 1;
this.top.deleteFront(); //Suppose, this method is available in jLLpackage
}
else {
System.out.print("Stack Underflow");
}
return data;
}
// Example 22.10:
Defining the method isEmpty()
boolean isEmpty(){
if (this.top.isEmpty()) {
return true;
}
else {
return false;
}
}
// Example 22.11:
Defining the method printStack()
void printStack() {
if (this.top.isEmpty()) {
System.out.print("Stack is
Empty");
}
else {
this.top.printList();
}
}
} // End of the
definition of the class StackL
// The main program
illustrating the linked list implementation of stack
// Example 22.12:
Basic Stack operation using the class StackL
/* This is the main program, illustration the
usage of the class defined. You should include the package, where this program
is stored. */
class StackLImplementationDemo
{
public static void main(String[] args) {
StackL<Integer> st = new StackL<Integer>();
st.push(5);
st.printStack();
st.push(6);
st.push(7);
st.printStack();
st.pop();
st.printStack();
st.pop();
st.printStack();
st.pop();
}
} // End of the demo class
// Example 22.13: An
application of stack to convert infix arithmetic expression to its postfix
notation. This example considers the linked list implementation of stack.
class InfixToPostfixDemo {
/* The following program defines a function
to return precedence of a given operator. Higher returned value means higher
precedence. */
static int precedence(char ch) {
switch (ch) {
case '+':
case '-':
return 1;
case '*':
case '/':
return 2;
case '^':
return 3;
}
return -1;
}
/* The method that converts given an infix
expression to its postfix equivalent expression. This method considers an expression in the
form of a String object. */
static String infixToPostfix(String exp) {
// initializing empty String for result
String result = new String("");
/* Create a stack which is initially empty.
We assume the linked lust implementation
of stack, defined in
Lecture #18-19. */
StackL<Character> stack = new StackL<>();
for (int i = 0; i<exp.length(); ++i) {
char c = exp.charAt(i);
// If the scanned character is an operand,
add it to output.
if (Character.isLetterOrDigit(c)) // The method is defined in java.util.*
result += c; // Append it to the
output expression
// If the scanned
character is an '(', push it to the stack.
else if (c == '(' )
stack.push(c);
/* If the scanned character is an ')',
pop and output from the stack until
an '(' is
encountered. */
else if (c == ')') {
while (!stack.isEmpty() && stack.peek() != '(' )
result += stack.pop();
if (!stack.isEmpty() && stack.peek() != '(')
return "Invalid
Expression"; // invalid expression
else
stack.pop();
}
else // an operator is encountered {
while (!stack.isEmpty() && precedence(c) <= precedence(stack.peek())){
if(stack.peek() == '(' )
return "Invalid
expression: Quit";
result += stack.pop();
}
stack.push(c);
}
} // End of for loop, when the entire input
expression is fully scanned
// pop all the operators from the stack
while (!stack.isEmpty()). {
if(stack.peek() == '(' )
return "Invalid expression";
result += stack.pop();
}
return result;
} // End of the method
// The main method to show a demo of
conversion
public static void main(String[] args) {
String
exp = "a+b*(c^d-e)^(f+g*h)-i";
System.out.println(infixToPostfix(exp));
}
} // End of the program